// 版权归Go作者所有。版权所有。
// 此源代码的使用受BSD样式
// 许可证的约束，该许可证可以在许可证文件中找到。

package pkginit

import (
	"bytes"
	"container/heap"
	"fmt"

	"cmd/compile/internal/base"
	"cmd/compile/internal/ir"
)

// 包初始化
// 
// 这里我们实现了对包级变量
// 初始化进行排序的算法。该规范是根据变量
// 初始化来编写的，但是由单个
// 赋值初始化的多个变量是一起处理的，因此这里我们将重点介绍
// 对初始化赋值的排序。很方便，这很好地映射到我们如何使用节点
// AST表示包级初始化。作业分为三个阶段：未开始、待定或完成。对于挂起阶段的赋值，我们使用Xoffset to 
// 记录尚未完成初始化赋值的唯一变量依赖项的数量。我们还维护一个
// “阻塞”映射，将分配映射回依赖它的所有分配
// 。
// 
// 例如，对于初始化，如：
// 
// var x=f（a，b，b）
// var a，b=g（）
// 
// “x=f（a，b，b）”赋值取决于两个变量（a和b），
// 因此其Xoffset将为2。相应地，“a，b=g（）”
// 赋值的“阻塞”条目将有两个条目返回到x的
// 赋值。
// 
// 从逻辑上讲，初始化是通过（1）获取所有未启动的
// 赋值，计算它们的依赖关系，并将它们标记为
// 挂起；（2） 将Xoffset==0的所有挂起的分配添加到
// /“就绪”优先级队列（按变量声明位置排序）；
// 和（3）迭代处理来自
// 队列的下一个挂起的分配，减少其阻止的分配的Xoffset，如果减为0，则将它们添加到队列中。
// 
// 作为一种优化，我们实际上将这三个步骤中的每一个应用于
// 每个作业。这会产生相同的顺序，但会降低队列大小
// 从而降低堆操作成本。

// 静态初始化阶段。
// 这些值存储在节点中的两位中。旗帜。
const (
	InitNotStarted = iota
	InitDone
	InitPending
)

type InitOrder struct {
	// 阻塞将初始化分配映射到依赖它的分配
	// 上。
	blocking map[ir.Node][]ir.Node

	// ready是等待初始化的分配队列。
	ready declOrder

	order map[ir.Node]int
}

// initOrder计算一系列
// 包级声明的初始化顺序（按声明顺序），并输出
// 包含在init（）函数
// 正文中的相应语句列表。
func initOrder(l []ir.Node) []ir.Node {
	var res ir.Nodes
	o := InitOrder{
		blocking: make(map[ir.Node][]ir.Node),
		order:    make(map[ir.Node]int),
	}

	// 按声明顺序处理所有包级分配。
	for _, n := range l {
		switch n.Op() {
		case ir.OAS, ir.OAS2DOTTYPE, ir.OAS2FUNC, ir.OAS2MAPR, ir.OAS2RECV:
			o.processAssign(n)
			o.flushReady(func(n ir.Node) { res.Append(n) })
		case ir.ODCLCONST, ir.ODCLFUNC, ir.ODCLTYPE:
			// nop 
		default:
			base.Fatalf("unexpected package-level statement: %v", n)
		}
	}

	// 检查所有作业是否已完成；如果没有，那么肯定有一个依赖循环。
	for _, n := range l {
		switch n.Op() {
		case ir.OAS, ir.OAS2DOTTYPE, ir.OAS2FUNC, ir.OAS2MAPR, ir.OAS2RECV:
			if o.order[n] != orderDone {
				// 如果已经打印了错误
				// 这些错误可能会让我们感到困惑，并且可能没有一个循环。让用户先修复这些
				// 文件。
				base.ExitIfErrors()

				o.findInitLoopAndExit(firstLHS(n), new([]*ir.Name), new(ir.NameSet))
				base.Fatalf("initialization unfinished, but failed to identify loop")
			}
		}
	}

	// 不变一致性检查。如果这不是零，那么我们应该在上面找到一个循环。
	if len(o.blocking) != 0 {
		base.Fatalf("expected empty map: %v", o.blocking)
	}

	return res
}

func (o *InitOrder) processAssign(n ir.Node) {
	if _, ok := o.order[n]; ok {
		base.Fatalf("unexpected state: %v, %v", n, o.order[n])
	}
	o.order[n] = 0

	// 计算变量依赖的数量并构建
	// 反向依赖（“阻塞”）图。
	for dep := range collectDeps(n, true) {
		defn := dep.Defn
		// 跳过函数依赖项（PFUNC）和
		// 变量已初始化（InitDone）。
		if dep.Class != ir.PEXTERN || o.order[defn] == orderDone {
			continue
		}
		o.order[n]++
		o.blocking[defn] = append(o.blocking[defn], n)
	}

	if o.order[n] == 0 {
		heap.Push(&o.ready, n)
	}
}

const orderDone = -1000

// flushReady重复将initialize应用于最早的（在
// 声明顺序中）分配，准备初始化并更新
// 反向依赖（“阻塞”）图。
func (o *InitOrder) flushReady(initialize func(ir.Node)) {
	for o.ready.Len() != 0 {
		n := heap.Pop(&o.ready).(ir.Node)
		if order, ok := o.order[n]; !ok || order != 0 {
			base.Fatalf("unexpected state: %v, %v, %v", n, ok, order)
		}

		initialize(n)
		o.order[n] = orderDone

		blocked := o.blocking[n]
		delete(o.blocking, n)

		for _, m := range blocked {
			if o.order[m]--; o.order[m] == 0 {
				heap.Push(&o.ready, m)
			}
		}
	}
}

// findInitLoopAndExit搜索包含变量
// 或函数n的初始化循环。如果找到，它会将该循环报告为错误并退出。
// 
// 路径指向用于跟踪
// 访问的变量/函数序列的切片。使用指向片的指针可以使
// 片容量增长并限制重新分配。
func (o *InitOrder) findInitLoopAndExit(n *ir.Name, path *[]*ir.Name, ok *ir.NameSet) {
	for i, x := range *path {
		if x == n {
			reportInitLoopAndExit((*path)[i:])
			return
		}
	}

	// 可能有多个涉及n的循环；通过对
	// 引用进行排序，我们可以确定地选择报告的引用。
	refers := collectDeps(n.Defn, false).Sorted(func(ni, nj *ir.Name) bool {
		return ni.Pos().Before(nj.Pos())
	})

	*path = append(*path, n)
	for _, ref := range refers {
		// 已初始化的短路变量。
		if ref.Class == ir.PEXTERN && o.order[ref.Defn] == orderDone || ok.Has(ref) {
			continue
		}

		o.findInitLoopAndExit(ref, path, ok)
	}

	// n不参与循环。
	// 记录该事实，以避免在以另一种方式到达时再次检查它，否则该遍历将花费指数时间遍历所有路径
	// 通过与循环相关的包调用图部分。
	ok.Add(n)

	*path = (*path)[:len(*path)-1]
}

// reportInitLoopAndExit将报告和初始化循环作为错误
// 并退出。然而，如果l实际上不是一个初始化循环，那么它只返回
// 即可。
func reportInitLoopAndExit(l []*ir.Name) {
	// 旋转循环，使最早的变量声明位于起始位置
	// 处。
	i := -1
	for j, n := range l {
		if n.Class == ir.PEXTERN && (i == -1 || n.Pos().Before(l[i].Pos())) {
			i = j
		}
	}
	if i == -1 {
		// 假阳性：循环只涉及递归
		// 函数。返回，以便findInitLoop可以继续
		// 搜索。
		return
	}
	l = append(l[i:], l[:i]...)

	// TODO（mdempsky）：方法值打印为“T.m-fm”而不是“T.m”。想办法避免这种情况。

	var msg bytes.Buffer
	fmt.Fprintf(&msg, "initialization loop:\n")
	for _, n := range l {
		fmt.Fprintf(&msg, "\t%v: %v refers to\n", ir.Line(n), n)
	}
	fmt.Fprintf(&msg, "\t%v: %v", ir.Line(l[0]), l[0])

	base.ErrorfAt(l[0].Pos(), msg.String())
	base.ErrorExit()
}

// collectDeps返回声明n所依赖的所有包级函数和
// 变量。如果transitive为true，则
// 那么它还包括任何依赖的
// 对函数（但不是变量）的传递依赖关系。
func collectDeps(n ir.Node, transitive bool) ir.NameSet {
	d := initDeps{transitive: transitive}
	switch n.Op() {
	case ir.OAS:
		n := n.(*ir.AssignStmt)
		d.inspect(n.Y)
	case ir.OAS2DOTTYPE, ir.OAS2FUNC, ir.OAS2MAPR, ir.OAS2RECV:
		n := n.(*ir.AssignListStmt)
		d.inspect(n.Rhs[0])
	case ir.ODCLFUNC:
		n := n.(*ir.Func)
		d.inspectList(n.Body)
	default:
		base.Fatalf("unexpected Op: %v", n.Op())
	}
	return d.seen
}

type initDeps struct {
	transitive bool
	seen       ir.NameSet
	cvisit     func(ir.Node)
}

func (d *initDeps) cachedVisit() func(ir.Node) {
	if d.cvisit == nil {
		d.cvisit = d.visit // 缓存关闭
	}
	return d.cvisit
}

func (d *initDeps) inspect(n ir.Node)      { ir.Visit(n, d.cachedVisit()) }
func (d *initDeps) inspectList(l ir.Nodes) { ir.VisitList(l, d.cachedVisit()) }

// 访问调用任何包级函数或变量的foundDep 
// 由n引用（如果有）。
func (d *initDeps) visit(n ir.Node) {
	switch n.Op() {
	case ir.ONAME:
		n := n.(*ir.Name)
		switch n.Class {
		case ir.PEXTERN, ir.PFUNC:
			d.foundDep(n)
		}

	case ir.OCLOSURE:
		n := n.(*ir.ClosureExpr)
		d.inspectList(n.Func.Body)

	case ir.ODOTMETH, ir.OMETHVALUE, ir.OMETHEXPR:
		d.foundDep(ir.MethodExprName(n))
	}
}

// foundDep记录我们通过将n添加到
// seen中发现了对n的依赖。
func (d *initDeps) foundDep(n *ir.Name) {
	// 可以在涉及接口
	// 类型的方法表达式中发生；e、 g.已修复缺陷/问题4495。去
	if n == nil {
		return
	}

	// 没有定义的名称就
	// 初始化顺序而言并不有趣。
	if n.Defn == nil {
		return
	}

	if d.seen.Has(n) {
		return
	}
	d.seen.Add(n)
	if d.transitive && n.Class == ir.PFUNC {
		d.inspectList(n.Defn.(*ir.Func).Body)
	}
}

// declOrder实现堆。接口，根据第一个LHS表达式的位置对赋值语句
// 进行排序。
// 
// N.B.，使用第一个LHS表达式的位置，因为
// OAS节点的位置可能不唯一。例如，给定
// 声明“var a，b=f（），g（）”，“a”必须在“b”之前排序，
// 但是两个OAS节点都使用“=”标记的位置作为其位置。
type declOrder []ir.Node

func (s declOrder) Len() int { return len(s) }
func (s declOrder) Less(i, j int) bool {
	return firstLHS(s[i]).Pos().Before(firstLHS(s[j]).Pos())
}
func (s declOrder) Swap(i, j int) { s[i], s[j] = s[j], s[i] }

func (s *declOrder) Push(x interface{}) { *s = append(*s, x.(ir.Node)) }
func (s *declOrder) Pop() interface{} {
	n := (*s)[len(*s)-1]
	*s = (*s)[:len(*s)-1]
	return n
}

// firstLHS返回
// 赋值左边的第一个表达式
func firstLHS(n ir.Node) *ir.Name {
	switch n.Op() {
	case ir.OAS:
		n := n.(*ir.AssignStmt)
		return n.X.Name()
	case ir.OAS2DOTTYPE, ir.OAS2FUNC, ir.OAS2RECV, ir.OAS2MAPR:
		n := n.(*ir.AssignListStmt)
		return n.Lhs[0].Name()
	}

	base.Fatalf("unexpected Op: %v", n.Op())
	return nil
}
